home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
EnigmA Amiga Run 1996 February
/
EnigmA AMIGA RUN 04 (1996)(G.R. Edizioni)(IT)[!][issue 1996-02][Skylink CD III].iso
/
earcd
/
program
/
mkdpnd11.lha
/
MkDepend-1.1
/
nodes.c
< prev
next >
Wrap
C/C++ Source or Header
|
1995-09-19
|
11KB
|
478 lines
/*
$VER: nodes:c 1.0 (10-Sep-95) Copyright © by Lars Düning
*/
/*---------------------------------------------------------------------------
** Management of the dependency tree and nodes.
**
** Copyright © 1995 Lars Düning - All rights reserved.
** Permission granted for non-commercial use.
**---------------------------------------------------------------------------
** Each file (source or include) is associated one node which is kept in
** a binary search tree with the name as index. Glued to each node is
** a list of that nodes which files the master nodes includes.
** Each node contains an extra node pointer the module uses to implement
** tree-independant lists, namely the TODO list of files still to read
** and a virtual stack for inorder tree traversals.
*
** Adding and retrieving the files to analyse is done using the functions
** nodes_addsource()
** nodes_depend()
** nodes_todo()
**
** The output of the dependency tree is done inorder using
** nodes_initwalk()
** nodes_inorder()
**
** The list of dependencies for one single node is managed using
** nodes_deplist()
** nodes_freelist()
**
** Tree traversal and creation must not be mixed!
**---------------------------------------------------------------------------
** C: DICE 3.01
**---------------------------------------------------------------------------
** [lars] Lars Düning; Am Wendenwehr 25; D-38114-Braunschweig;
** Germany; Tel. 49-531-345692
**---------------------------------------------------------------------------
** 10-Sep-95 [lars] v 1.0
** 10-Sep-95 [lars] current
**---------------------------------------------------------------------------
*/
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "nodes.h"
/*-------------------------------------------------------------------------*/
/* Types for block allocation of Nodes and NodeRefs.
* Note that Nodes are never freed.
*/
#define NBLOCKSIZE 16
typedef struct nodeblock
{
struct nodeblock * pNext; /* Next nodeblock */
int iFree; /* Number of first free node */
Node aNodes[NBLOCKSIZE]; /* Block of nodes */
}
NodeBlock;
#define RBLOCKSIZE 16
typedef struct refblock
{
struct refblock * pNext; /* Next refblock */
int iFree; /* Number of first free noderef */
NodeRef aRefs[NBLOCKSIZE]; /* Block of noderefs */
}
RefBlock;
/*-------------------------------------------------------------------------*/
static NodeBlock *pFreeNBlocks = NULL; /* Nodeblocks */
static RefBlock *pFreeRBlocks = NULL; /* Refblocks */
static NodeRef *pFreeRefs = NULL; /* List of free NodeRefs */
static Node *pTree = NULL; /* Dependency tree */
static Node *pList = NULL; /* List of (tree) nodes */
/* The List is used as TODO list for the files to analyse as well as
* stack simulation for the tree traversal.
*/
/*-------------------------------------------------------------------------*/
static Node *
nodes_newnode (void)
/* Allocate a new Node.
*
* Result:
* Pointer to the new Node, or NULL on error.
*
* The memory of the Node is cleared, except for .flags which is set
* to NODE_NEW.
*/
{
Node * pNode;
if (!pFreeNBlocks || !pFreeNBlocks->iFree)
{
NodeBlock * pNewBlock;
pNewBlock = (NodeBlock *)malloc(sizeof(*pNewBlock));
if (!pNewBlock)
return NULL;
memset(pNewBlock, 0, sizeof(*pNewBlock));
pNewBlock->iFree = NBLOCKSIZE;
pNewBlock->pNext = pFreeNBlocks;
pFreeNBlocks = pNewBlock;
}
pNode = &(pFreeNBlocks->aNodes[--pFreeNBlocks->iFree]);
pNode->flags |= NODE_NEW;
return pNode;
}
/*-------------------------------------------------------------------------*/
static NodeRef *
nodes_newref (void)
/* Allocate a new NodeRef.
*
* Result:
* Pointer to the new NodeRef, or NULL on error.
*
* The memory of the NodeRef is cleared.
*/
{
NodeRef * pRef;
if (pFreeRefs)
{
pRef = pFreeRefs;
pFreeRefs = pRef->pNext;
}
else
{
if (!pFreeRBlocks || !pFreeRBlocks->iFree)
{
RefBlock * pNewBlock;
pNewBlock = (RefBlock *)malloc(sizeof(*pNewBlock));
if (!pNewBlock)
return NULL;
pNewBlock->iFree = NBLOCKSIZE;
pNewBlock->pNext = pFreeRBlocks;
pFreeRBlocks = pNewBlock;
}
pRef = &(pFreeRBlocks->aRefs[--pFreeRBlocks->iFree]);
}
memset(pRef, 0, sizeof(*pRef));
return pRef;
}
/*-------------------------------------------------------------------------*/
static void
nodes_freeref (NodeRef * pRef)
/* Free a NodeRef.
*
* pRef: Pointer to the NodeRef to free.
*/
{
assert(pRef);
pRef->pNext = pFreeRefs;
pFreeRefs = pRef;
}
/*-------------------------------------------------------------------------*/
static Node *
nodes_findadd (const char *pName)
/* Find the node associated with file *pName. If necessary, add the node.
*
* pName: Pointer to the filename of the node.
*
* Result:
* Pointer to the node associated with this filename, or NULL on error.
*
* If the nodes has been added by this call, NODE_NEW is set in its .flags.
*/
{
Node * pThis, * pPrev;
int i;
assert(pName);
pPrev = NULL;
if (!pTree)
{
pTree = nodes_newnode();
return pTree;
}
pThis = pTree;
while(pThis)
{
i = strcmp(pThis->pName, pName);
if (!i)
return pThis;
pPrev = pThis;
if (i > 0)
pThis = pThis->pLeft;
else
pThis = pThis->pRight;
}
pThis = nodes_newnode();
if (pThis)
{
if (i > 0)
pPrev->pLeft = pThis;
else
pPrev->pRight = pThis;
}
return pThis;
}
/*-------------------------------------------------------------------------*/
int
nodes_addsource (const char *pName, int bAvoid)
/* Add a source file to the dependency tree.
*
* pName : Name of the file to add.
* bAvoid: True if the file is explicitely _no_ sourcefile.
*
* Result:
* 0 on success, non-0 on error (out of memory).
*
* The file is also added to the internal TODO list of files.
*/
{
Node *pNode;
assert(pName);
pNode = nodes_findadd(pName);
if (!pNode)
return 1;
if (pNode->flags & NODE_NEW)
{
pNode->flags = NODE_SOURCE;
pNode->pName = strdup(pName);
if (!pNode->pName)
return 1;
if (!bAvoid)
{
pNode->pNext = pList;
pList = pNode;
}
}
if (bAvoid)
pNode->flags |= NODE_AVOID;
return 0;
}
/*-------------------------------------------------------------------------*/
int
nodes_depend (Node * pDepender, const char * pName)
/* Add file *pName to the list of dependees of *pDepender.
*
* pDepender: Node which depends on the file given.
* pName : Name of the file pDepender depends on.
*
* Result:
* 0 on success, non-0 on error (out of memory).
*
* The file is added to the dependee-list and is also inserted into the
* dependency tree and the TODO list to compute nested dependencies.
*/
{
Node * pNode;
NodeRef * pRef;
assert(pDepender);
assert(pName);
pNode = nodes_findadd(pName);
if (!pNode)
return 1;
if (pNode->flags & NODE_NEW)
{
pNode->flags = 0;
pNode->pName = strdup(pName);
if (!pNode->pName)
return 1;
pNode->pNext = pList;
pList = pNode;
}
/* Add pNode to pDependers->pDeps if not already there */
for ( pRef = pDepender->pDeps
; pRef && pRef->pNode != pNode
; pRef = pRef->pNext
);
if (!pRef)
{
pRef = nodes_newref();
if (!pRef)
return 1;
pRef->pNode = pNode;
pRef->pNext = pDepender->pDeps;
pDepender->pDeps = pRef;
}
return 0;
}
/*-------------------------------------------------------------------------*/
Node *
nodes_todo (void)
/* Return the tree node of the next file to analyse.
*
* Result:
* Pointer to the node of the next file to analyse, or NULL if there is
* none.
*/
{
Node * pNode;
/* NODE_DONE should not happen, but checking it is free */
while (pList && (pList->flags & (NODE_AVOID|NODE_DONE)))
pList = pList->pNext;
if (pList)
{
pNode = pList;
pList = pList->pNext;
pNode->flags |= NODE_DONE;
}
else
pNode = NULL;
return pNode;
}
/*-------------------------------------------------------------------------*/
void
nodes_initwalk (void)
/* Initialise a tree traversal.
*/
{
assert(!pList);
pList = pTree;
if (pList)
{
pList->iStage = 0;
pList->pNext = NULL;
}
}
/*-------------------------------------------------------------------------*/
Node *
nodes_inorder (void)
/* Return the next Node of an inorder tree traversal.
*
* Result:
* Pointer to the next node, or NULL if traversal is complete.
*/
{
Node *pNode;
if (!pList)
return NULL;
while (pList)
{
switch (pList->iStage)
{
case 0:
pList->iStage++;
pNode = pList->pLeft;
break;
case 1:
pList->iStage++;
return pList;
break;
case 2:
pList->iStage++;
pNode = pList->pRight;
break;
case 3:
pList = pList->pNext;
pNode = NULL;
break;
default:
assert(0);
break;
}
if (pNode)
{
pNode->pNext = pList;
pList = pNode;
pNode->iStage = 0;
}
}
return NULL;
}
/*-------------------------------------------------------------------------*/
NodeRef *
nodes_deplist (Node * pNode)
/* Gather the list of dependees of *pNode.
*
* Result:
* Pointer to the list of dependees, or NULL if an error occurs.
* First entry in the list is pNode itself.
*/
{
NodeRef *pDList;
NodeRef *pMark;
NodeRef *pThis;
NodeRef *pRover;
Node *pDep;
assert(pNode);
pDList = nodes_newref();
if (!pDList)
return NULL;
/* The list of dependencies is gathered in a wide search. */
pDList->pNode = pNode;
NODES_MARK(pNode);
for ( pThis = pDList, pMark = pDList
; pMark
; pMark = pMark->pNext
)
{
for ( pRover = pMark->pNode->pDeps
; pRover
; pRover = pRover->pNext
)
{
pDep = pRover->pNode;
if (!NODES_MARKED(pDep))
{
pThis->pNext = nodes_newref();
if (!pThis->pNext)
return NULL;
pThis = pThis->pNext;
pThis->pNode = pDep;
NODES_MARK(pDep);
}
}
}
return pDList;
}
/*-------------------------------------------------------------------------*/
void
nodes_freelist (NodeRef * pDList)
/* Free a dependency list earlier produced by nodes_deplist().
*
* pDList: Base of the list to free.
*/
{
NodeRef * pThis;
while (pDList)
{
NODES_UNMARK(pDList->pNode);
pThis = pDList;
pDList = pDList->pNext;
pThis->pNext = pFreeRefs;
pFreeRefs = pThis;
}
}
/***************************************************************************/